package LeetCode刷题.暑假刷的算法;

/**
 * @program: Java_Study
 * @author: Xiaofan
 * @createTime: 2021-08-24 15:45
 * @description: Functions of this class is 找出一组数中缺失的数
 **/
public class 缺失的数 {
    public static void main(String args[]) {
        int nums[] = {1, 2, 4, 5, 6};
        System.out.println("缺失的两个数字为：" + getDecreaseNum1(nums));

    }

    /**
     * 异或法！！！！重要*********
     */
    private static int getDecreaseNum1(int nums[]) {
        int num = 0;
        int maxNum = Integer.MIN_VALUE;
        for (int i = 0; i < nums.length; i++) {
            if (i > maxNum) {
                maxNum = i;//同时找出最大的那个数字
            }
            num ^= i;//先把所有的元素统统异或一遍
        }
        int sum = 0;
        for (int i = 1; i <= maxNum; i++) {
            sum ^= i;//然后求出从1到最大数字所有元素的异或
        }
        return sum ^ num;
    }


    //累加求和法
    private static int getDecreaseNum(int nums[]) {
        int maxNum = Integer.MIN_VALUE;
        int sum = 0;
        for (int i : nums) {
            if (i > maxNum) {
                maxNum = i;
            }
            sum += i;
        }
        int tot = 0;
        for (int i = 1; i <= maxNum; i++) {
            tot += i;
        }
        return tot - sum;
    }
}